//给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。 
//
// 
//
// 示例 1： 
//
// 
//输入：head = [1,2,3,4,5], k = 2
//输出：[4,5,1,2,3]
// 
//
// 示例 2： 
//
// 
//输入：head = [0,1,2], k = 4
//输出：[2,0,1]
// 
//
// 
//
// 提示： 
//
// 
// 链表中节点的数目在范围 [0, 500] 内 
// -100 <= Node.val <= 100 
// 0 <= k <= 2 * 10⁹ 
// 
// Related Topics 链表 双指针 👍 792 👎 0


package com.cjl.leetcode.editor.cn;
/**
 * [P61]_旋转链表
 * @author cjl
 * @date 2022-06-26 19:00:38
 */
public class P61_RotateList{
      public static void main(String[] args) {
            //测试代码
           Solution solution = new P61_RotateList().new Solution();
      }
      //力扣代码
      //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    /**
     * 解题思路：双指针
     * 注意：N个元素移动，是第二个指针达到边界后，与第一个指针后的元素被移动；
     * @param head
     * @param k
     * @return
     */
    public ListNode rotateRight(ListNode head, int k) {
        if(null == head || null == head.next){
            return head;
        }
        ListNode yNode = new ListNode();
        yNode.next = head;
        ListNode first = head;
        ListNode second = head;
        int t = 0;
        //t =0; first =1, second = 2;
        //t =1; first = 1, second =3;
        while (t < k && second.next != null){
            second = second.next;
            t++;
        }
        //t =2;
        if(t == k){ //链表长度> k；
            //first = 1, second = 3;
            // first = 2, second =4;
            //first =3, second = 5;
            while (second.next != null){
                first = first.next;
                second = second.next;
            }
            second.next = yNode.next;
            yNode.next = first.next;
            first.next = null;
            return yNode.next;
        }else if( t == k -1){ //链表长度 == k
            return yNode.next;
        }else { //链表长度 < k
            int realK = k%(t+1);
            return rotateRight(head, realK);
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)

    class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
  }